//设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存
//被填满时，它应该删除最近最少使用的项目。
//
// 它应该支持以下操作： 获取数据 get 和 写入数据 put 。
//
// 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
//写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新
//的数据值留出空间。
//
// 示例:
//
// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1);       // 返回  1
//cache.put(3, 3);    // 该操作会使得密钥 2 作废
//cache.get(2);       // 返回 -1 (未找到)
//cache.put(4, 4);    // 该操作会使得密钥 1 作废
//cache.get(1);       // 返回 -1 (未找到)
//cache.get(3);       // 返回  3
//cache.get(4);       // 返回  4
//
// Related Topics 设计 哈希表 链表 双向链表 👍 142 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;


//Java：LRU 缓存
public class LruCacheLcci {
    public static void main(String[] args) {

        LRUCache cache = new LruCacheLcci().new LRUCache(2);
        // TO TEST

        cache.put(1, 1);
        cache.put(2, 2);

        cache.get(1);
        cache.put(3, 3);
        cache.show();
    }
//leetcode submit region begin(Prohibit modification and deletion)

    class LRUCache {
        class Node {
            public Node() {
            }

            public Node(int key, int value) {
                this.value = value;
                this.key = key;
            }

            int key;
            int value;
            Node pre;
            Node next;
        }

        class LinkedNode {
            Node head;
            Node tail;

            public LinkedNode() {
                this.head = new Node();
                this.tail = new Node();
                head.next = tail;
                tail.pre = head;
            }

            public void addOnHead(Node node) {
                node.next = head.next;
                node.next.pre = node;
                head.next = node;
                node.pre = head;
            }

            public void deleteNode(Node node) {
                node.next.pre = node.pre;
                node.pre.next = node.next;
                node.pre = null;
                node.next = null;
            }

            public Node deleteTailElement() {
                Node tailElement = tail.pre;
                deleteNode(tail.pre);
                return tailElement;
            }

            public void showCache() {
                Node node = head.next;
                while (node != tail) {
                    System.out.print(node.value + " ");
                    node = node.next;
                }
            }
        }
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public void show() {
            linkedNode.showCache();
        }
        private final int capacity;
        private final Map<Integer, Node> cache = new HashMap<>();
        private final LinkedNode linkedNode = new LinkedNode();

        public int get(int key) {
            Node node = cache.get(key);
            if (node == null)
                return -1;
            linkedNode.deleteNode(node);
            linkedNode.addOnHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            Node node;
            if (cache.containsKey(key)) {
                node = cache.get(key);
                node.value = value;
                linkedNode.deleteNode(node);
            } else {
                if (cache.size() == capacity) {
                    node = linkedNode.deleteTailElement();
                    cache.remove(node.key);
                    node.value = value;
                    node.key = key;

                } else {
                    node = new Node(key, value);
                }
                cache.put(key, node);
            }
            linkedNode.addOnHead(node);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)


}
